﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BinarySearchTrees
{

    public class BinarySearchTree
    {
        public BinaryTreeNode Root { get; set; }

        public BinarySearchTree()
        {
            this.Root = null;
        }

        public BinaryTreeNode Insert(BinaryTreeNode node, int value)
        {
            if (node == null)
            {
                return new BinaryTreeNode(value);
            }
            else if (value < node.Data)
            {
                node.Left = Insert(node.Left, value);
            }
            else if (value > node.Data)
            {
                node.Right = Insert(node.Right, value);
            }

            return node;
        }
        /// <summary>
        /// In-Order: Left child, Root, Right child
        /// </summary>
        public void InOrder(BinaryTreeNode node)
        {
            if (node != null)
            {
                InOrder(node.Left);
                node.DisplayNode();
                InOrder(node.Right);
            }
        }
        /// <summary>
        /// Pre-Order: Root, Left child, Right child
        /// </summary>
        public void PreOrder(BinaryTreeNode node)
        {
            if (node != null)
            {
                node.DisplayNode();
                PreOrder(node.Left);
                PreOrder(node.Right);
            }

        }
        /// <summary>
        /// Post-Order: Left Child, Right child, Root
        /// </summary>
        public void PostOrder(BinaryTreeNode node)
        {
            if (node != null)
            {
                PostOrder(node.Left);
                PostOrder(node.Right);
                node.DisplayNode();
            }
        }

        public int FindMin(BinaryTreeNode node)
        {
            while (node != null && node.Left != null)
            {
                node = node.Left;
            }

            return node.Data;
        }

        public int FindMax(BinaryTreeNode node)
        {
            while (node != null && node.Right != null)
            {
                node = node.Right;
            }

            return node.Data;
        }

        public bool Find(BinaryTreeNode node, int value)
        {
            if (node == null)
                return false;
            else if (value == node.Data)
                return true;
            else if (value <= node.Data)
                return Find(node.Left, value);
            else if (value >= node.Data)
                return Find(node.Right, value);
            else
                return false;
        }

        public void InLevel(BinaryTreeNode node)
        {
            Queue<BinaryTreeNode> q = new Queue<BinaryTreeNode>();
            q.Enqueue(node);

            while (q.Count > 0)
            {
                BinaryTreeNode tn = q.Dequeue();
                tn.DisplayNode();

                if (tn.Left != null)
                    q.Enqueue(tn.Left);
                if (tn.Right != null)
                    q.Enqueue(tn.Right);
            }
        }

        public void PrintOutsideFramework(BinaryTreeNode node)
        {
            if (node == null)
                return;
            if (node.Left == null && node.Right == null)
            {
                node.DisplayNode();
                return;
            }

            BinaryTreeNode root = node;

            root.DisplayNode();
            PrintOutsideFramework(node.Left);
            PrintOutsideFramework(node.Right);

            if (root.Left!=null)
                PrintOutsideFramework(root.Left);
        }

        public BinaryTreeNode LowestCommonAncestor(BinaryTreeNode btNode, BinaryTreeNode p, BinaryTreeNode q)
        {

            if (btNode == null)
                return null;
            if ((btNode == p || btNode == q))
            {
                Console.WriteLine("p or q is the root.  Root: {0} - p: {1} - q: {2}", btNode.Data, p.Data, q.Data);
                return btNode;
            }
            else
            {
                Console.WriteLine("Getting the LCA of p and q in left subtree. Current node: {0}", btNode.Data);
                BinaryTreeNode left = LowestCommonAncestor(btNode.Left, p, q);
                Console.WriteLine("Getting the LCA of p and q in right subtree. Current node: {0}", btNode.Data);
                BinaryTreeNode right = LowestCommonAncestor(btNode.Right, p, q);


                if (left != null && right != null)
                {
                    Console.WriteLine("If p ({0}) or q ({1})is in leftsubtree and other is in right", p.Data, q.Data);
                    Console.WriteLine("then then root ({0}) it the LCA", btNode.Data);
                    return btNode;
                }
                else if (left != null)
                {
                    Console.WriteLine("else if left ({0}) is not null, left is LCA", left.Data);
                    return left;
                }
                else if (right != null)
                {
                    Console.WriteLine("else right ({0}) is LCA", right.Data);
                    return right;
                }
                else
                {
                    return null;
                }
            }
        }        

        public void InLevelSpiral(BinaryTreeNode node)
        {
            int levels = GetLevels(node);
            bool reversed = false;
            for (int i = 1; i <= levels; i++)
            {
                GivenLevelSpiral(node, i, reversed);
                reversed = !reversed;
            }
        }
        private void GivenLevelSpiral(BinaryTreeNode node, int level, bool reversed)
        {
            if (node == null)
                return;
            if (level == 1)
                Console.Write("{0} ", node.Data);

            if (level > 1)
            {
                if (reversed)
                {
                    GivenLevelSpiral(node.Left, level - 1, reversed);
                    GivenLevelSpiral(node.Right, level - 1, reversed);
                }
                else
                {
                    GivenLevelSpiral(node.Right, level - 1, reversed);
                    GivenLevelSpiral(node.Left, level - 1, reversed);
                }
            }
        }
        private int GetLevels(BinaryTreeNode node)
        {
            if (node == null)
                return 0;

            int left = GetLevels(node.Left) + 1;
            int right = GetLevels(node.Right) + 1;

            return left < right ? right : left;

        }

        public void MinimalBST(int[] input)
        {
            this.Root = Partition(input, 0, input.Length-1);
        }

        private BinaryTreeNode Partition(int[] input, int left, int rigth)
        {            
            if(rigth<left)
                return null;
                      
            int mid = (left + rigth) / 2;
            BinaryTreeNode node = new BinaryTreeNode(input[mid]);
            node.Left = Partition(input, left, mid - 1);
            node.Right = Partition(input, mid + 1, rigth);

            return node;
        }
    }

    public class BinaryTreeNode
    {
        public int Data { get; set; }
        public BinaryTreeNode Left { get; set; }
        public BinaryTreeNode Right { get; set; }

        public BinaryTreeNode()
        {
            this.Left = null;
            this.Left = null;
        }

        public BinaryTreeNode(int data)
            : this()
        {
            this.Data = data;
        }

        public BinaryTreeNode(int data, BinaryTreeNode left)
            : this(data)
        {
            this.Left = left;
        }

        public BinaryTreeNode(int data, BinaryTreeNode left, BinaryTreeNode right)
            : this(data, left)
        {
            this.Right = right;
        }

        public void DisplayNode()
        {
            if (this != null)
                Console.Write(string.Format("{0} ", this.Data));
        }
    }
}